The wavelet tree (Grossi et al. [SODA, 2003]) and wavelet matrix (Claude etal. [Inf. Syst., 47:15--32, 2015]) are compact indices for texts over analphabet $[0,\sigma)$ that support rank, select and access queries in $O(\lg\sigma)$ time. We first present new practical sequential and parallelalgorithms for wavelet tree construction. Their unifying characteristics isthat they construct the wavelet tree bottomup}, i.e., they compute the lastlevel first. We also show that this bottom-up construction can easily beadapted to wavelet matrices. In practice, our best sequential algorithm is upto twice as fast as the currently fastest sequential wavelet tree constructionalgorithm (Shun [DCC, 2015]), simultaneously saving a factor of 2 in space.This scales up to 32 cores, where we are about equally fast as the currentlyfastest parallel wavelet tree construction algorithm (Labeit et al. [DCC,2016]), but still use only about 75 % of the space. An additional theoreticalresult shows how to adapt any wavelet tree construction algorithm to thewavelet matrix in the same (asymptotic) time, using only little extra space.
展开▼
机译：小波树（Grossi等人[SODA，2003]）和小波矩阵（Claude等人[Inf。Syst。，47：15--32，2015]）是字母$ [0，\ sigma]上文本的紧凑索引）$支持在$ O（\ lg \ sigma）$时间内排名，选择和访问查询。我们首先提出用于小波树构造的新的实用顺序算法和并行算法。它们的统一特征是它们构造了小波树的“自底向上”，即，它们首先计算了最后一级。我们还表明，这种自下而上的构造可以轻松地适应小波矩阵。在实践中，我们最好的顺序算法的速度是目前最快的顺序小波树构造算法的两倍（Shun [DCC，2015]），同时在空间上节省了2倍。这可以扩展到32个核，在这里我们大约相等速度与目前最快的并行小波树构造算法一样快（Labeit等人[DCC，2016]），但仍仅使用了约75％的空间。额外的理论结果显示了如何在几乎不增加空间的情况下，在相同（渐近）时间内使任何小波树构造算法适应小波矩阵。
展开▼
